package com.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author zhongyi_yang
 */
public class MergeSort {
	/**
	 * 归并排序
	 *
	 * @param dataWraps
	 */
	public static void mergeSort(DataWrap[] dataWraps) {
		sort(dataWraps, 0, dataWraps.length - 1);
	}

	/**
	 * 将索引从left到right范围的数组元素进行归并排序
	 *
	 * @param dataWraps 待排序的数组
	 * @param left      待排序的数组的第一个元素的索引
	 * @param right     待排序数组的最后一个元素的索引
	 */
	private static void sort(DataWrap[] dataWraps, int left, int right) {
		if (left < right) {
			// 找到中间索引
			int center = (left + right) / 2;
			// 对左边数组进行递归
			sort(dataWraps, left, center);
			// 对右边数组进行递归
			sort(dataWraps, center + 1, right);
			// 合并
			merge(dataWraps, left, center, right);
		}
	}

	/**
	 * 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序
	 *
	 * @param dataWraps 数组对象
	 * @param left      左数组的第一个元素的索引
	 * @param center    左数组的最后一个索引，center+1右数组的第一个元素的索引
	 * @param right     右数组的最后一个元素的索引
	 */
	private static void merge(DataWrap[] dataWraps, int left, int center,
							  int right) {
		// 定义一个与待排序序列长度相同的临时数组
		DataWrap[] tmpArrDataWraps = new DataWrap[dataWraps.length];
		int mid = center + 1;
		// third记录中间数组的索引
		int third = left;
		int tmp = left;
		while (left <= center && mid <= right) {
			// 从练歌数组中取小的放入中间数组
			if (dataWraps[left].compareTo(dataWraps[mid]) <= 0) {
				tmpArrDataWraps[third++] = dataWraps[left++];
			} else {
				tmpArrDataWraps[third++] = dataWraps[mid++];
			}
		}
		// 剩余部分依次放入中间数组
		while (mid <= right) {
			tmpArrDataWraps[third++] = dataWraps[mid++];
		}
		while (left <= center) {
			tmpArrDataWraps[third++] = dataWraps[left++];
		}
		// 将中间数组中的内容复制回原来数组
		// （原left至right范围内的内容复制回原数组）
		while (tmp <= right) {
			dataWraps[tmp] = tmpArrDataWraps[tmp++];
		}
	}

	public static void main(String[] args) {
		DataWrap dataWrap[] = {new DataWrap(9, ""), new DataWrap(-16, ""),
				new DataWrap(21, "*"), new DataWrap(23, ""),
				new DataWrap(-30, ""), new DataWrap(-49, ""),
				new DataWrap(21, ""), new DataWrap(30, "*"),
				new DataWrap(30, "")};
		System.out.println("排序前：" + Arrays.toString(dataWrap));
		mergeSort(dataWrap);
		System.out.println("排序后：" + Arrays.toString(dataWrap));
	}
}
